class MiniHeap {
    constructor() {
        this.heap = []
    }
    // 插入
    insert(num) {
        this.heap.push(num)
        this.upBubble()
    }
    // 拾取最小值
    pickUpMin() {
        if(this.heap.length === 0) return undefined;
        if(this.heap.length === 1) return this.heap.pop();

        let min = this.heap[0]
        this.heap[0] = this.heap.pop()
        this.downSink()
        return min

    }

    // 向上冒泡, 排序
    upBubble(){
        let index = this.heap.length - 1
        while(index > 0) {
            let parentIndex = Math.floor((index - 1)/2)
            if(parentIndex >= 0 && this.heap[parentIndex] > this.heap[index]) {
                // swap
                [this.heap[parentIndex], this.heap[index]] = [this.heap[index], this.heap[parentIndex]]
                index = parentIndex
            } else {
                break
            }
        }
    }

    // 下沉
    downSink(){
        let index = 0
        let length = this.heap.length
        while(1) {
            let leftIndex = 2 * index + 1
            let rightIndex = 2 * index + 2
            let miniIndex = index
            if(leftIndex <= length - 1 && this.heap[leftIndex] < this.heap[miniIndex]) {
                miniIndex = leftIndex
            }
            if(rightIndex <= length - 1 && this.heap[rightIndex] < this.heap[miniIndex]) {
                miniIndex = rightIndex
            }
            if(miniIndex === index) break
            [this.heap[index], this.heap[miniIndex]] = [this.heap[miniIndex], this.heap[index]]
            index = miniIndex
        }
    }
}

let miniHeap = new MiniHeap();
miniHeap.insert(5)
miniHeap.insert(2)
miniHeap.insert(4)
miniHeap.insert(7)

console.log("------>>>", miniHeap.heap)
console.log("------>>>", miniHeap.pickUpMin())
console.log("------>>>", miniHeap.heap)
